{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fb31c427",
   "metadata": {},
   "source": [
    "# 题目"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "222fa02c",
   "metadata": {},
   "source": [
    "给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。\n",
    "\n",
    "示例 1:\n",
    "输入: s = \"abcabcbb\"\n",
    "输出: 3 \n",
    "解释: 因为无重复字符的最长子串是 \"abc\"，所以其长度为 3。\n",
    "\n",
    "示例 2:\n",
    "输入: s = \"bbbbb\"\n",
    "输出: 1\n",
    "解释: 因为无重复字符的最长子串是 \"b\"，所以其长度为 1。\n",
    "\n",
    "示例 3:\n",
    "输入: s = \"pwwkew\"\n",
    "输出: 3\n",
    "解释: 因为无重复字符的最长子串是 \"wke\"，所以其长度为 3。\n",
    "     请注意，你的答案必须是子串的长度，\"pwke\" 是一个子序列，不是子串。\n",
    " \n",
    "提示：\n",
    "0 <= s.length <= 5 * 104\n",
    "s 由英文字母、数字、符号和空格组成\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "59825d28",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_duplicate(text: str) -> int:\n",
    "    char_list = [set(()) for _ in text]\n",
    "    for idx, ch in enumerate(text):\n",
    "        if idx == 0:\n",
    "            char_list[idx] = set((ch))\n",
    "            continue\n",
    "        if ch in char_list[idx-1]:\n",
    "            char_list[idx] = set((ch))\n",
    "        else:\n",
    "            char_list[idx] = char_list[idx-1].copy()\n",
    "            char_list[idx].add(ch)\n",
    "\n",
    "    max_cnt = 0\n",
    "    for ch_set in char_list:\n",
    "        max_cnt = max(max_cnt, len(ch_set))\n",
    "    return max_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "ca249317",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_duplicate_v2(text: str) -> int:\n",
    "    max_cnt, left = 0, 0\n",
    "    charset = set()\n",
    "    for idx, ch in enumerate(text):\n",
    "        if ch in charset:\n",
    "            # 碰到重复字符\n",
    "            print(idx-1, left, charset)\n",
    "            max_cnt = max(len(charset), max_cnt)\n",
    "            for j in range(left, idx):\n",
    "                charset.remove(text[j])\n",
    "                if text[j] == ch:\n",
    "                    left = j + 1\n",
    "                    break\n",
    "\n",
    "        charset.add(ch)\n",
    "\n",
    "    print(left, charset)\n",
    "    max_cnt = max(len(charset), max_cnt)\n",
    "    return max_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "067b494c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def length_of_longest_substring(s: str) -> int:\n",
    "    char_set = set()  # 存储当前窗口的唯一字符\n",
    "    left = 0          # 窗口左边界\n",
    "    max_length = 0    # 记录最大长度\n",
    "\n",
    "    for right in range(len(s)):\n",
    "        # 当字符重复时，右移左指针并移除字符，直到无重复\n",
    "        while s[right] in char_set:\n",
    "            char_set.remove(s[left])\n",
    "            left += 1\n",
    "        # 将当前字符加入窗口，并更新最大长度\n",
    "        char_set.add(s[right])\n",
    "        max_length = max(max_length, right - left + 1)\n",
    "\n",
    "    return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "28a7d98c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abcabcbb\"\n",
    "find_duplicate(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "94edae84",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"bbbbb\"\n",
    "find_duplicate(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "7eef6de4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"pwwkew\"\n",
    "find_duplicate(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f5f0f68f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"\"\n",
    "find_duplicate(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "9c4e093f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abace\"\n",
    "find_duplicate(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "4c998f7f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_longest_substring(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "df637c48",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0 {'a', 'b'}\n",
      "1 {'e', 'a', 'b', 'c'}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_duplicate_v2(s)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
